// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-28 22:26
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetcodeRepeat;

import java.util.HashMap;
import java.util.Map;

public class LongestSubsequence {
    /**
     * 最长定差子数组计算
     * 通过给定子树组，计算给定子数组中的定差数列的最长长度
     * core: 因为是定差的，所以可以通过HashMap快速定位上一个状态元素
     */
    public int longestSubsequenceT(int[] arr, int difference) {
        int n = arr.length, max = Integer.MIN_VALUE;
        int[] f = new int[n];
        Map<Integer, Integer> map = new HashMap<>();
        map.put(arr[0], 1);
        for (int i = 1; i < n; i++) {
            f[i] = 1;
            if (map.containsKey(arr[i] - difference)) {
                f[i] = map.get(arr[i] - difference) + 1;
            }
            max = Math.max(max, f[i]);
            map.put(arr[i], f[i]);
        }
        return max;
    }

    /**
     * 使用HashMap代替状态数组
     * 因为是定差数列，所以使用Map可以快速定位到上一个元素
     */
    public int longestSubsequence(int[] arr, int difference) {
        int n = arr.length, max = 1;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(arr[0], 1);
        for (int i = 1; i < n; i++) {
            map.put(arr[i], map.getOrDefault(arr[i] - difference, 0) + 1);
            max = Math.max(max, map.get(arr[i]));
        }
        return max;
    }
}
